class Solution {//LCR114——火星词典
public:
    string alienOrder(vector<string>& words) {
        int n=words.size();
        //创建邻接表和入度表
        unordered_map<char,unordered_set<char>> edges;
        unordered_map<char,int> in;
        for(auto str:words){//初始化入度表
            for(auto ch:str){
                in[ch]=0;
            }
        }

        for(int i=0;i<n;i++){//建表
            for(int j=i+1;j<n;j++){
                int k=0;
                while(k<words[i].size()&&k<words[j].size()){
                    int ch1=words[i][k],ch2=words[j][k];
                    if(ch1!=ch2){//找到关系
                        auto[x,y]=edges[ch1].insert(ch2);
                        if(y==true) in[ch2]++;
                        break;
                    }
                    k++;
                }
                if(k<words[i].size()&&k==words[j].size()) return "";
            }
        }

        queue<char> q;
        for(auto [x,y]:in){
            if(y==0){
                q.push(x);
            }
        }
        string ret;
        while(q.size()){
            char t=q.front();
            q.pop();
            ret.push_back(t);
            for(char e:edges[t]){
                in[e]--;
                if(in[e]==0){
                    q.push(e);
                }
            }
        }
        for(auto [x,y]:in){//遍历入度表
            if(y!=0){
                return "";
            } 
        }
        return ret;

    }
};